package Hot_100;

import org.junit.Test;

public class T55_canJump {
    boolean flag=false;

    @Test
    public void test() {
        System.out.println(canJump_1(new int[]{3,2,1,0,4}));
    }

//    ---------------------法3:贪心------------------------------
    public boolean canJump_3(int[] nums) {
        int arrival=0;     //arrival表示最远可到达的位置
        for (int i = 0; i < nums.length; i++) {
            if (i > arrival) { //如果i大于当前可到达的最远位置，则什么该处不可到达
                return false;
            }
            arrival = Math.max(i + nums[i], arrival); //更新最远可到达的距离，arrival表示由前i个元素能到达的最远距离
        }
        return true;
    }


//    ---------------------法2: dp ------------------------------
    public boolean canJump_2(int[] nums) {
        boolean[] dp = new boolean[nums.length];    //标记当前位置是否可达
        dp[0] = true;
        for (int i = 1; i < nums.length; i++) {     //dp[i]是否可达，需要判断前i-1个位置是否存在能到达i的位置
            for (int j = 0; j < i; j++) {
                if (dp[j] && nums[j] + j >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[dp.length - 1];
    }


//    ---------------------法1: dfs （超时了！！）------------------------------
    public boolean canJump_1(int[] nums) {
        DFS(nums, 0);
        return flag;
    }

    void DFS(int[] nums, int index) {
        if (index >= nums.length - 1) {
            flag=true;
            return;
        }

        if (nums[index] == 0) { // 当 index<nums.length-1
            return;
        }

        for (int i = 1; i <= nums[index]; i++) {
            DFS(nums, index + i);
        }
    }
}
